<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>2707. 字符串中的额外字符</title>
</head>
<body>
  <script>
//     给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。

// 请你采取最优策略分割 s ，使剩下的字符 最少 。

 

// 示例 1：

// 输入：s = "leetscode", dictionary = ["leet","code","leetcode"]
// 输出：1
// 解释：将 s 分成两个子字符串：下标从 0 到 3 的 "leet" 和下标从 5 到 8 的 "code" 。只有 1 个字符没有使用（下标为 4），所以我们返回 1 。
// 示例 2：

// 输入：s = "sayhelloworld", dictionary = ["hello","world"]
// 输出：3
// 解释：将 s 分成两个子字符串：下标从 3 到 7 的 "hello" 和下标从 8 到 12 的 "world" 。下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。
 

// 提示：

// 1 <= s.length <= 50
// 1 <= dictionary.length <= 50
// 1 <= dictionary[i].length <= 50
// dictionary[i] 和 s 只包含小写英文字母。
// dictionary 中的单词互不相同。

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {number}
 */
 var minExtraChar = function(s, dictionary) {
// dp[i] 表示到 s[0]...s[i] 的字符串采取最优策略分割方案，剩下的字符数。
    const dp = new Array(s.length + 1).fill(0)
    for (let i = 0; i < s.length; i ++) {
        const cur = s.slice(0, i + 1)
        // 默认是在 s[0]...s[i - 1] 的基础上增加 s[i]
        dp[i + 1] = dp[i] + 1
        for (const word of dictionary) {
            // 如果存在满足情况的单词，取最优解
            if (cur.endsWith(word)) {
                dp[i + 1] = Math.min(dp[i + 1], dp[i - word.length + 1])
            }
        }
    }
    return dp[s.length]
};
  </script>
</body>
</html>